"""
912. 排序数组--快速排序
     * 快速排序
     * 思路：快速排序可以看成一个树的遍历，相当于每次从数组中找到一个元素，将其放到指定的位置，
     * 这个位置满足：左边所有元素 < 当前元素 < 右边所有元素
     * 快速排序的过程是一个构造二叉搜索树的过程
"""
from typing import List


class QuickSort:

    def sortArray(self, nums: List[int]) -> List[int]:
        self.quick_sort(nums, 0, len(nums) - 1)
        return nums

    def quick_sort(self, nums: List[int], low: int, high: int):
        """
        快速排序框架
        @param nums: 待排数组
        @param low: 下标
        @param high: 上标
        """
        if low >= high:
            return

        # 先将其中一个元素排好，使“左边所有元素 < 当前元素 < 右边所有元素”
        i = self.find_sort_nums(nums, low, high)

        # 排序左边
        self.quick_sort(nums, low, i - 1)

        # 排序右边
        self.quick_sort(nums, i + 1, high)

    def find_sort_nums(self, nums: List[int], low: int, high: int) -> int:
        """
         * 从nums中选择一个元素，使其满足 左边所有元素 < 当前元素 < 右边所有元素
         * 做法：选择第一个元素作为待排序的元素，利用双指针将low放到合适的位置，
         * 1. i指向low + 1，j指向high，
         * 2. 分别让nums[i]和nums[low]比较，nums[j]和nums[low]比较，当nums[low] < nums[i] 且 nums[high] > nums[i]，交换i和j的位置
         *    最后再交换low和j位置的元素
        @param nums: 待排数组
        @param low: 下标
        @param high: 上标
        """
        # 取第一个元素作为待排序元素
        sort_num = nums[low]

        # 利用双指针将low放到合适的位置
        i = low + 1
        j = high
        while i <= j:
            while i < high and nums[i] <= sort_num:
                i += 1
            while j > low and nums[j] > sort_num:
                j -= 1
            if i >= j:
                break
            # 交换i j 的元素
            self.swap(nums, i, j)

        # 交换low和j
        self.swap(nums, low, j)

        return j



    def swap(self, nums: List[int], i: int, j: int):
        """
        交换i j两个元素
        """
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp


